package NO1_Array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 2025-08-28
 * 力扣 - 57. 插入区间
 * <p>
 * 给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，
 * 并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
 * 在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。
 * 返回插入之后的 intervals。
 * 注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。
 */
public class InsertRangesMain {
    public static void main(String[] args) {
        int[][] intervals = {{1, 3}, {6, 9}};
        int[] newInterval = {2, 5};
        System.out.println(Arrays.toString(insert(intervals, newInterval)));
    }

    // 所有结束位置小于新区间开始位置的区间直接加入结果（这些区间在新区间左边）
    // 找到第一个结束位置大于新区间开始位置的区间，合并区间
    // 所有开始位置大于合并后区间结束位置（这些区间在新区间右边）
    public static int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int n = intervals.length;

        // 1. 添加所有在新区间左边的区间（完全不重叠）
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }

        // 2. 合并所有与新区间重叠的区间
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval);

        // 3. 添加所有在新区间右边的区间（完全不重叠）
        while (i < n) {
            result.add(intervals[i]);
            i++;
        }

        return result.toArray(new int[result.size()][]);
    }


    public static int[][] insert1(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        boolean inserted = Boolean.FALSE; // 标记新区间是否已经插入

        for (int[] current : intervals) {
            if (current[1] < newInterval[0]) {
                // 当前区间完全在新区间左边，不重叠
                result.add(current);
            } else if (current[0] > newInterval[1]) {
                // 当前区间完全在新区间右边，不重叠
                // 先插入新区间（如果还没插入的话）
                if (!inserted) {
                    result.add(newInterval);
                    inserted = Boolean.TRUE;
                }
                result.add(current);
            } else {
                // 当前区间与新区间重叠，合并它们
                newInterval[0] = Math.min(newInterval[0], current[0]);
                newInterval[1] = Math.max(newInterval[1], current[1]);
            }
        }

        // 如果遍历完所有区间后新区间还没插入（比如新区间在所有区间之后）
        if (!inserted) {
            result.add(newInterval);
        }

        return result.toArray(new int[result.size()][]);
    }
}
